/***********************************************************************
 * Copyright © 2013 Beals Software
 * All Rights Reserved
************************************************************************
Author: Donald Beals
Date: August 28, 2013
Description: Helper functions for the Polygon-based Pathfinding Library.
polygonpathfinding.codeplex.com
****************************** Change Log ******************************
08.28.13 - Created initial file. (dbeals)
***********************************************************************/

function isPointInsidePolygon(polygonPoints, testX, testY)
{
	var counter = 0;
	var point1 = polygonPoints[0];
	for(var index = 1; index <= polygonPoints.length; ++index)
	{
		var point2 = polygonPoints[index % polygonPoints.length];
		if(testY > Math.min(point1.y, point2.y) &&
			testY <= Math.max(point1.y, point2.y) &&
			testX <= Math.max(point1.x, point2.x) &&
			point1.y != point2.y)
		{
			var xinters = (testY - point1.y) * (point2.x - point1.x) / (point2.y - point1.y) + point1.x;
			if(point1.x == point2.x || testX <= xinters)
				++counter;
		}
		point1 = point2;
	}
	return counter % 2 != 0;
}

function isRectangleInsidePolygon(polygonPoints, node)
{
	return (isPointInsidePolygon(polygonPoints, node.x, node.y) 
			&& isPointInsidePolygon(polygonPoints, node.x + node.width, node.y + node.height)) ||
		(isPointInsidePolygon(polygonPoints, node.x + node.width, node.y)
			&& isPointInsidePolygon(polygonPoints, node.x, node.y + node.height));
}

function findMinMax(polygonPoints)
{
	var minX = Number.MAX_VALUE;
	var minY = Number.MAX_VALUE;
	var maxX = Number.MIN_VALUE;
	var maxY = Number.MIN_VALUE;
	
	for(var index = 0; index < polygonPoints.length; ++index)
	{
		var point = polygonPoints[index];		
		if(point.x < minX)
			minX = point.x;
		if(point.y < minY)
			minY = point.y;
			
		if(point.x > maxX)
			maxX = point.x;
		if(point.y > maxY)
			maxY = point.y;
	}
	
	return [ new Point(minX, minY), new Point(maxX, maxY) ];
}

function findBounds(polygonPoints)
{
	var minMax = findMinMax(polygonPoints);
	return new Rectangle(minMax[0].x, minMax[0].y, minMax[1].x - minMax[0].x, minMax[1].y - minMax[0].y);
}

function createGrid(polygonPoints, nodeWidth, nodeHeight)
{
	var bounds = findBounds(polygonPoints);
	var gridWidth = Math.ceil(bounds.width / nodeWidth);
	var gridHeight = Math.ceil(bounds.height / nodeHeight);
	
	var output = new Array(gridWidth * gridHeight);
	for(var row = 0; row < gridHeight; ++row)
	{
		for(var column = 0; column < gridWidth; ++column)
		{
			var nodeBounds = new Rectangle(bounds.x + (column * nodeWidth), bounds.y + (row * nodeHeight), nodeWidth, nodeHeight);
			var isValid = isRectangleInsidePolygon(polygonPoints, nodeBounds);
			output[(row * gridWidth) + column] =
			{
				'bounds': nodeBounds,
				'isValid': isValid,
			};
		}
	}
	
	return {
		'nodes': output,
		'gridWidth': gridWidth,
		'gridHeight': gridHeight,
	};
}